package jianzhiOffer;
//剑指 Offer 13. 机器人的运动范围
public class Num13_movingCount {
    int m;
    int n;
    int k;
    boolean [][] used  ;
    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        this.k =k;
        this.used = new boolean[m][n];
        return dfs(0 , 0 );
    }
    public int dfs(int i, int j) {
        if (i >= m || j >= n || used[i][j] || Sum(i) + Sum(j) > k  ){
            return 0;
        }
        used[i][j] = true;
        return 1 + dfs(i + 1 , j ) +dfs(i , j + 1 ) ;

    }
    private  int Sum(int i) {
        int sum = 0;
        while (i > 0){
            sum += i % 10;
            i /= 10;
        }
        return sum;
    }

}
